// https://leetcode.cn/problems/keep-multiplying-found-values-by-two/description/?envType=daily-question&envId=2025-11-19

// 算法思路总结：
// 1. 先对数组排序，便于二分查找
// 2. 使用二分查找在数组中查找当前original值
// 3. 找到后将original加倍，并更新查找起始位置left
// 4. 利用有序性，后续查找从上一次找到的位置开始
// 5. 时间复杂度：O(NlogN + KlogN)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    bool binarySearch(vector<int>& nums, int& left, int right, int target)
    {
        int l = left - 1, r = right + 1;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (nums[mid] == target)
            {
                left = mid;
                return true;
            }
            else if (nums[mid] < target)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }
        return false;
    }

    int findFinalValue(vector<int>& nums, int original) 
    {
        int m = nums.size();
        sort(nums.begin(), nums.end());

        int left = 0;
        while (binarySearch(nums, left, m - 1, original))
        {
            original *= 2;
        }

        return original;
    }
};

int main()
{
    Solution sol;

    vector<int> nums1 = {5,3,6,1,12}; 
    vector<int> nums2 = {2,7,9};
    int original1 = 3, original2 = 4;

    cout << sol.findFinalValue(nums1, original1) << endl;
    cout << sol.findFinalValue(nums2, original2) << endl;

    return 0;
}